|
In automata theory (a branch of computer science), DFA minimization is the task of transforming a given deterministic finite automaton (DFA) into an equivalent DFA that has a minimum number of states. Here, two DFAs are called equivalent if they recognize the same regular language. Several different algorithms accomplishing this task are known and described in standard textbooks on automata theory.〔Hopcroft, Ullman (1979)〕 ==Minimum DFA== For each regular language that can be accepted by a DFA, there exists a minimal automaton, a DFA with a minimum number of states and this DFA is unique (except that states can be given different names.)〔, Section 4.4.3, "Minimization of DFA's", p. 159, and p. 164 (remark after Theorem 4.26)〕 The minimal DFA ensures minimal computational cost for tasks such as pattern matching. There are two classes of states that can be removed/merged from the original DFA without affecting the language it accepts to minimize it. * Unreachable states are those states that are not reachable from the initial state of the DFA, for any input string. * Nondistinguishable states are those that cannot be distinguished from one another for any input string. DFA minimization is usually done in three steps, corresponding to the removal/merger of the relevant states. Since the elimination of nondistinguishable states is computationally the most expensive one, it is usually done as the last step. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「DFA minimization」の詳細全文を読む スポンサード リンク
|